//Given a string s that contains parentheses and letters, remove the minimum 
//number of invalid parentheses to make the input string valid. 
//
// Return all the possible results. You may return the answer in any order. 
//
// 
// Example 1: 
//
// 
//Input: s = "()())()"
//Output: ["(())()","()()()"]
// 
//
// Example 2: 
//
// 
//Input: s = "(a)())()"
//Output: ["(a())()","(a)()()"]
// 
//
// Example 3: 
//
// 
//Input: s = ")("
//Output: [""]
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 25 
// s consists of lowercase English letters and parentheses '(' and ')'. 
// There will be at most 20 parentheses in s. 
// 
// Related Topics 广度优先搜索 字符串 回溯 👍 623 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class P301RemoveInvalidParentheses {
    public static void main(String[] args) {
        Solution solution = new P301RemoveInvalidParentheses().new Solution();
        System.out.println(solution.removeInvalidParentheses(")("));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Set<String> set = new HashSet<>();
        int n, max, len;
        String s;

        public List<String> removeInvalidParentheses(String _s) {
            s = _s;
            n = s.length();
            int l = 0, r = 0;
            for (char c : s.toCharArray()) {
                if (c == '(') l++;
                else if (c == ')') r++;
            }
            max = Math.min(l, r);
            dfs(0, "", 0);
            return new ArrayList<>(set);
        }

        void dfs(int u, String cur, int score) {
            if (score < 0 || score > max) return;
            if (u == n) {
                if (score == 0 && cur.length() >= len) {
                    if (cur.length() > len) set.clear();
                    len = cur.length();
                    set.add(cur);
                }
                return;
            }
            char c = s.charAt(u);
            if (c == '(') {
                dfs(u + 1, cur + String.valueOf(c), score + 1);
                dfs(u + 1, cur, score);
            } else if (c == ')') {
                dfs(u + 1, cur + String.valueOf(c), score - 1);
                dfs(u + 1, cur, score);
            } else {
                dfs(u + 1, cur + String.valueOf(c), score);
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}